#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<queue>
#include<assert.h>
using namespace std;
#define maxV 100
#define maxsize 100
typedef struct node
{
	int data;
	struct node *left;
    struct node *right;
}*tree;
tree newNode(int data){
    tree node=(tree)malloc(sizeof(struct node));
    node->data=data;
    node->left=NULL;
    node->right=NULL;
    return node;
}
tree create_bst(tree root,int data){
    if(root==NULL)
        return newNode(data);
    if(root->data>data)
        root->left=create_bst(root->left,data);
    else
        root->right=create_bst(root->right,data);
    return root;
}
void preOrder(tree root){
    stack<tree> s;
    s.push(root);
    while(!s.empty()){
        tree node=s.top();
        printf("%d ",node->data);
        s.pop();
        if(node->right) s.push(node->right);
        if(node->left) s.push(node->left);
    }
}
bool path(tree root,tree p,stack<tree> &s){
    tree curNode=root,pre=NULL;
    if(root==NULL||p==NULL||!s.empty()){
        return false;
    }
    while(curNode||!s.empty()){
        while(curNode){
            s.push(curNode);
            if(curNode==p)
                return true;
            curNode=curNode->left;
        }
        if(!s.empty()){
            curNode=s.top();
            while(curNode->right==NULL||curNode->right==pre){//curNode的右孩子为空，或者右孩子已经被访问
                pre=s.top();
                s.pop();
                curNode=s.top();
            }
            //curNode结点的右孩子没有被访问
            curNode=curNode->right;
        }
    }
    return false;
}

typedef struct Enode{
    int adjVex;
    struct Enode *next;
}*en;
typedef struct Vnode{
    char data;
    struct Enode *firstArc;
}*vn,adjList[maxV];
typedef struct agraph{
    int vNum,eNum;
    adjList vertices;
}graph;
void createGraph(graph *g){
    int i,j,k;
    printf("请输入顶点个数和边的条数:");
    scanf("%d %d",&g->vNum,&g->eNum);
    printf("请输入顶点信息:");
    for(k=0;k<g->vNum;k++){
        getchar();
        scanf("%c",&g->vertices[k].data);
        g->vertices[k].firstArc=NULL;
    }
    printf("请输入边vi和vj的关系(例如：0 1表示g->vertices[0].data--g->vertices[1].data有边)\n");
    for(k=0;k<g->eNum;k++){
        scanf("%d %d",&i,&j);
        en enode=(en)malloc(sizeof(struct Enode));
        enode->adjVex=j;
        //头插法
        enode->next=g->vertices[i].firstArc;
        g->vertices[i].firstArc=enode;

        // 如果是无向图
        enode =(en)malloc(sizeof(struct Enode));
        enode->adjVex=i;
        enode->next=g->vertices[j].firstArc;
        g->vertices[j].firstArc=enode;
    }
}
bool visited[maxsize];
queue<int> Q;  
int FirstNeighbor(graph g,int v){
    if(g.vertices[v].firstArc)
        return g.vertices[v].firstArc->adjVex;
    else
        return -1;
}
int NextNeighbor(graph g,int w,int v){
    en p=g.vertices[v].firstArc;
    while(p->adjVex!=w){
        p=p->next;
    }
    if(p->next)
        return p->next->adjVex;
    else 
        return -1;
}
void visit(graph g,int v){
    printf("%c->",g.vertices[v].data);
}
void bfs(graph g,int v){//先访问再入队，再出队
    visit(g,v);
    Q.push(v);
    visited[v]=true;
    while(!Q.empty()){
        v=Q.front();
        Q.pop();
        // for(int w=FirstNeighbor(g,v);w>=0;w=NextNeighbor(g,w,v)){
        //     if(!visited[w]){
        //         visit(g,w);
        //         visited[w]=true;
        //         Q.push(w);
        //     }
        // }
        for(en p=g.vertices[v].firstArc;p!=NULL;p=p->next){
            if(!visited[p->adjVex]){
                visit(g,p->adjVex);
                visited[p->adjVex]=true;
                Q.push(p->adjVex);
            }
        }
    }
    
}
void bfs_traverse(graph g){
    for(int i=0;i<g.vNum;i++){//顶点标记数组初始化
        visited[i]=false;
    }
    for(int i=0;i<g.vNum;i++){
        if(!visited[i]){
            bfs(g,i);
        }
    }
}


void dfs(graph g,int v){
    visit(g,v);
    visited[v]=true;
    for(int w=FirstNeighbor(g,v);w>=0;w=NextNeighbor(g,w,v)){
        if(!visited[w]){
            dfs(g,w);
        }
    }

}
void dfs_traverse(graph g){
    for(int i=0;i<g.vNum;i++){
        visited[i]=false;
    }
    for(int i=0;i<g.vNum;i++){
        if(!visited[i]){
            dfs(g,i);
        }
    }
}

stack<int> s;
void dfs_iterative(graph g,int v){//先入栈，再访问再退栈循环
    s.push(v);
    while(!s.empty()){
        v=s.top();
        visit(g,v);
        visited[v]=true;
        s.pop();
        for(int w=FirstNeighbor(g,v);w>=0;w=NextNeighbor(g,w,v)){
            if(!visited[w]){
                s.push(w);
            }
        }
    }
}
void dfs_traverse_iterative(graph g){
     for(int i=0;i<g.vNum;i++){
        visited[i]=false;
    }
    for(int i=0;i<g.vNum;i++){
        if(!visited[i]){
            dfs_iterative(g,i);
        }
    }
}

int inDegree(graph g,int v){
    int in=0;
    for(int i=0;i<g.vNum;i++){
        for(int w=FirstNeighbor(g,i);w>=0;w=NextNeighbor(g,w,i)){
            if(w==v)
                in++;
        }
    }
    return in;
}
void delp(tree &root,tree p){
    assert(root);
    /*
    assert 的作用是现计算表达式 expression ，如果其值为假（即为0），那么它先向 stderr 打印一条出错信息,然后通过调用 abort 来终止程序运行。
    使用 assert 的缺点是，频繁的调用会极大的影响程序的性能，增加额外的开销。
    在调试结束后，可以通过在包含 #include 的语句之前插入 #define NDEBUG 来禁用 assert 调用
    */
    if(root==NULL)
        return;
    if(root->data>p->data){
        delp(root->left,p);
    }else if(root->data<p->data){
        delp(root->right,p);
    }else{
        tree node=root;//记录要删除的结点
        if(root->left==NULL){
            root=root->right;
            free(node);
        }else if(root->right==NULL){
            root=root->left;
            free(node);
        }else{
            tree replace = root->right;
            while(replace->left){
                replace=replace->left;
            }
            root->data=replace->data;
            delp(root->right,p);
        }
    }
}
int main(){  
    /*
           10
        /     \ 
      2        49
       \       / \
        3     20  78
        \    / \
         8  11 21
         \
          8
    */
    int a[10]={10,2,3,49,8,20,78,21,8,11};
    tree root=NULL;
    for(int i=0;i<10;i++)
        root=create_bst(root,a[i]);
    // preOrder(root);
    delp(root,root->right);
    // BSTreeRemoveR(&root,root->right);
    printf("\n删除后:");
    preOrder(root);

    // stack<tree> s;  
    // path(root,root->right->left->right,s);
    // printf("\nroot->p的路径是：");
    // while(!s.empty()){
    //     printf("%d ",s.top()->data);
    //     s.pop();
    // }

    graph g;
    createGraph(&g);
    printf("\nbfs:");
    bfs_traverse(g);
    // printf("\ndfs:");
    // dfs_traverse(g);
    // printf("\ndfs非递归:");
    // dfs_traverse_iterative(g);
    // printf("\n度数为%d",inDegree(g,3));
    // int arr[maxsize];
    // for(int i=0;i<g.vNum;i++){
    //     arr[i]=inDegree(g,i);
    //     printf("%d ",arr[i]);
    // }
    return 0;
}